package com.dangdang.recursion.test0805;

import java.util.*;

/**
 * @Author Jiangnan Hou
 * @Date 2022/8/5
 */
public class DFS {

    public List<List<Integer>> combine(int n, int k){
        List<List<Integer>> res = new ArrayList<>();
        if (n<=-1 || k>n) {
            return null;
        }
        Deque<Integer> path = new ArrayDeque<>();

        dfs(n,k,0,res,path);

        return res;
    }

    private void dfs(int n,int k,int begin,List<List<Integer>> res, Deque<Integer> path) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i=begin;i<n;i++) {
            path.add(i+1);
            dfs(n,k,i+1,res,path);
            path.removeLast();
        }

    }

    public void dfsList(List<List<String>> couponInfos,int index,List<List<String>> result,Deque composition){
/*        if (composition.size() == couponInfos.size()) {
            result.add(new ArrayList<>(composition));
            return;
        }

            for (int i=index;i<couponInfos.size(); i++) {
                for (int j=0;j<couponInfos.get(i).size();j++) {
                    composition.add(couponInfos.get(i).get(j));
                    dfsList(couponInfos,i+1,result,composition);
                    composition.removeLast();
                }

            }*/


       if (composition.size() == couponInfos.size()) {
            result.add(new ArrayList<>(composition));
            return;
        }

        for (int j = 0; j < couponInfos.get(index).size(); j++) {
            composition.add(couponInfos.get(index).get(j));
            dfsList(couponInfos, index + 1, result, composition);
            composition.removeLast();
        }



/*        if (composition.size() == couponInfos.size()) {
            result.add(new ArrayList<>(composition));
        }else {
            for (int j = 0; j < couponInfos.get(index).size(); j++) {
                composition.add(couponInfos.get(index).get(j));
                dfsList(couponInfos, index + 1, result, composition);
                composition.removeLast();
            }
        }*/
    }


    public static void main(String[] args) {
        DFS dfs = new DFS();
        //System.out.println(dfs.combine(4,2));

        List<List<String>> couponInfos = new ArrayList<>();
        String[] c1 = {"C1","C2","C3","C4"};
        String[] c2 = {"C5","C6","C7"};
        String[] c3 = {"C8","C9","C10","C11","C12"};
        couponInfos.add(Arrays.asList(c1));
        couponInfos.add(Arrays.asList(c2));
        couponInfos.add(Arrays.asList(c3));
        List<List<String>> result = new ArrayList<>();
        Deque<String> composition = new ArrayDeque();

        dfs.dfsList(couponInfos,0,result,composition);
        System.out.println(result);
        System.out.println(result.size());
    }
}
